package cn.edu.xjtu.work.rob;

/**
 * 213. 打家劫舍 II
 * 
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈
 * ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * 
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 */
public class SolutionII {
  public static void main(String[] args) {
    SolutionII solu = new SolutionII();
    int[] nums = { 2, 3, 2 };
    System.out.println(solu.rob(nums));
  }

  /**
   * 类似于打家劫舍I,但是第一间房子和最后一间房子挨着,所以要确保不能同时偷着两个房子,因此一次从第一个房子偷到倒数第二个,另一次从第二个偷到倒数第一个,两个取最大值就是最大金额
   * 
   * @param nums
   * @return
   */
  public int rob(int[] nums) {
    int length = nums.length;
    if (length == 1) {
      return nums[0];
    }
    if (length == 2) {
      return Math.max(nums[0], nums[1]);
    }

    return Math.max(robHelp(nums, 0, length - 2), robHelp(nums, 1, length - 1));
  }

  public int robHelp(int[] nums, int start, int end) {
    int[] dp = new int[end - start + 1];
    dp[0] = nums[start];
    dp[1] = Math.max(nums[start], nums[start + 1]);

    for (int i = 2; i < end - start + 1; i++) {
      dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i + start]);
    }
    return dp[dp.length - 1];
  }
}
